﻿#pragma once
#include "Index.h"

/**
 * 机器人运动范围.
 * https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=265&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu
 *
 * 地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。
 * 一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
 * 但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。
 * 例如，当threshold为 18 时，机器人能够进入方格[35,37] ，因为 3+5+3+7 = 18。
 * 但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
 *
 * 数据范围：0≤threshold≤15，1≤rows,cols≤100
 * 进阶：空间复杂度O(nm)，时间复杂度O(nm)
 */
namespace ReachableCountInMatrix
{
	class Question
	{
	public:
		virtual int movingCount(int threshold, int rows, int cols) = 0;
	};

	class DFS:public Question
	{
	public:
		int movingCount(int threshold, int rows, int cols) override
		{
			if (threshold < 0 || rows <= 0 || cols <= 0)
				return 0;

			_row = rows;
			_col = cols;
			_reachedGrids.clear();

			std::vector<std::pair<int, int>> expandable_grids;
			expandable_grids.emplace_back(0, 0);

			while(!expandable_grids.empty())
			{
				auto pos = expandable_grids.back();
				expandable_grids.pop_back();
				//标记pos可达
				_reachedGrids.insert(pos.first * 1000 + pos.second);

				//上、下、左、右四方向
				static std::vector<std::tuple<int, int>> dirs = {
					std::make_tuple(-1,0),
					std::make_tuple(1,0),
					std::make_tuple(0,-1),
					std::make_tuple(0,1),
				};
				for (auto& dir : dirs)
				{
					auto next_pos = std::make_pair(pos.first + std::get<0>(dir), pos.second + std::get<1>(dir));
					//沿方向移动的位置可达
					if(canReach(threshold, next_pos.first,next_pos.second))
					{
						expandable_grids.emplace_back(next_pos);
					}
				}
			}

			return _reachedGrids.size();
		}
	private:
		int canReach(int threshold, int x, int y)
		{
			//越界
			if (x < 0 || x >= _row || y < 0 || y >= _col)
				return false;

			//要满足位置的数位和不超过threshold
			int digits_sum = 0;
			while (x > 0)
			{
				digits_sum += x % 10;
				x /= 10;
			}
			while (y > 0)
			{
				digits_sum += y % 10;
				y /= 10;
			}
			if (digits_sum > threshold)
				return false;


			//位置还未到达过
			if (_reachedGrids.count(x * 1000 + y) > 0)
				return false;

			return true;
		}
	private:
		int _row, _col;
		std::unordered_set<int> _reachedGrids;
	};

	class DP:public Question
	{
	public:
		int movingCount(int threshold, int rows, int cols) override
		{
			int count_reach=0;

			std::vector<bool> dp_rows[2];
			dp_rows[0].resize(cols+1,false);
			dp_rows[1].resize(cols+1,false);

			for(int row_index=1;row_index<=rows;++row_index)
			{
				std::vector<bool>& row_cur=dp_rows[row_index%2];
				std::vector<bool>& row_pre=dp_rows[(row_index-1)%2];

				std::fill(row_cur.begin(),row_cur.end(),false);
				//矩阵的首个位置[0,0]起点,总是可达到
				if(row_index==1)
					row_cur[1]=true;
				for(int col_index=1;col_index<=cols;++col_index)
				{
					bool reachable=getDigitSum(row_index-1,col_index-1) <= threshold;
					if(reachable)
					{
						bool has_path=row_cur[col_index];
						has_path |=row_cur[col_index-1];
						has_path |=row_pre[col_index];
						row_cur[col_index]=has_path;
						if(has_path)
							count_reach++;
					}
				}
			}
			return count_reach;
		}
	private:
		//获取在指定行,列位置上的数位和
		int getDigitSum(int row,int col)
		{
			int digit_sum=0;
			while(row>0)
			{
				digit_sum+=row % 10;
				row/=10;
			}
			while(col>0)
			{
				digit_sum+=col % 10;
				col/=10;
			}
			return digit_sum;
		}
	};

	TEST(ReachableCountInMatrix,Normal)
	{
		TEST_SOLUTION1(Question,DP,&)
		{
			EXPECT_EQ(solution->movingCount(5,4,7),18);
			EXPECT_EQ(solution->movingCount(0,3,1),1);
			EXPECT_EQ(solution->movingCount(9,38,15),135);
		};
	}
}

